package 刷题.leedcode606;
//迭代
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.Set;

public class Solution {
    /**
     * 前序遍历：二叉树转化为括号和整数组成的字符串
     * 前序遍历：中左右
     * 利用队列，将经过的结点依次放入队列中
     * 对于当前栈顶的元素，如果没有遍历过，就把他放入集合中，
     * 并开始对以它为根的子树进行遍历
     * 1.如果当前节点有两个孩子，先将右孩子入栈，再将左孩子入栈
     * 2.只有左孩子，将左孩子入栈
     * 3.只有右孩子，要先添加一个（）表示左孩子为空，再将右孩子入栈
     * 4.如果没有孩子，那么什么都不用写
     */
    public String tree2str(TreeNode root){
        StringBuffer ans = new StringBuffer();//创建一个空StringBuffer对象
        //构造一个队列,双端队列的数组
        Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
        //将头结点放入栈中
        stack.push(root);//while循环条件，stack不为空
        Set<TreeNode> visited = new HashSet<TreeNode>();
        while(!stack.isEmpty()){
            //定义一个结点，用来保存stack中的数据
            TreeNode node = stack.peek();
            //如果node在visited中，返回true，不在，返回false
            if(visited.add(node)){
                if(node != root){
                    ans.append("(");
                }
                ans.append(node.val);
                //情况三
                if(node.left == null && node.right != null){
                    ans.append("()");
                }
                //先右后左，保证前序遍历
                if(node.right != null){
                    stack.push(node.right);
                }
                if(node.left != null){
                    stack.push(node.left);
                }
            }else{
                if(node != root){
                    ans.append(")");
                }
                stack.pop();//出栈
            }
        }
        return ans.toString();
    }
}
